package sort.leetcode;

/**
 * 快速排序的partition解决第k大元素问题
 */
public class Num215 {
    public int findKthLargest(int[] nums, int k) {
        // 第k大元素的索引为 n - k
        // [1,2,3,4,5] 第2大元素4对应的索引5 - 2 = 3
        return findKthLargestInternal(nums,0,nums.length - 1,nums.length - k);
    }

    /**
     * 在nums[l..r]找到索引为k的元素
     * @param nums
     * @param l
     * @param r
     * @param k
     * @return
     */
    private int findKthLargestInternal(int[] nums, int l, int r, int k) {
        if (l > r) {
            // 空区间
            return -1;
        }
        int p = partition(nums,l,r);
        if (p == k) {
            // 此时索引p对应的元素恰好就是要查找的元素
            return nums[p];
        }else if (k > p) {
            // 在右半区间接着找
            return findKthLargestInternal(nums,p + 1,r,k);
        }
        // 此时k < p,在左半区间找
        return findKthLargestInternal(nums,l,p - 1,k);
    }

    private int partition(int[] nums, int l, int r) {
        // 默认选择第一个元素作为分区点
        int v = nums[l];
        // i是当前处理的元素
        // arr[l + 1..j] < v
        // 最开始没有元素 < v
        int j = l;
        // arr[j + 1...i) >= v 也是空区间
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] < v) {
                swap(nums,j + 1,i);
                j ++;
            }
        }
        // j对应 < v的最后一个元素
        swap(nums,l,j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
